package BinaryTree.Easy;


import Structures.TreeNode;

import java.util.Stack;

public class LC0104 {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> depthStack = new Stack<>();

        nodeStack.add(root);
        depthStack.add(1);

        int maxDepth = -1;
        while (!nodeStack.empty()) {
            TreeNode node = nodeStack.pop();
            int depth = depthStack.pop();
            if (depth > maxDepth) maxDepth = depth;
            if (node.right != null) {
                nodeStack.add(node.right);
                depthStack.add(depth + 1);
            }
            if (node.left != null) {
                nodeStack.add(node.left);
                depthStack.add(depth + 1);
            }
        }

        return maxDepth;
    }
}
